package leetcode_301_400;

import com.sun.xml.internal.bind.v2.model.core.ID;

import java.util.*;

public class LeeCode_301_wrong {
    public static void main(String[] args) {
        System.out.println(removeInvalidParentheses("()())()"));
        System.out.println(removeInvalidParentheses("(a)())()"));
        System.out.println(removeInvalidParentheses(")("));
        System.out.println(removeInvalidParentheses("n"));
        System.out.println(removeInvalidParentheses(""));
        System.out.println(removeInvalidParentheses("(("));
        System.out.println(removeInvalidParentheses("(((k()(("));
        System.out.println(removeInvalidParentheses("()(()"));
        System.out.println(removeInvalidParentheses("(((()(()"));
    }
    private static List<String> removeInvalidParentheses(String S) {
        List<List<Integer>> list = new ArrayList<>();
        char[] s = S.toCharArray();
        int n = s.length;
        if (n == 0)
            return new ArrayList<>();
        int[] dp = new int[n];
        List<Integer> tmp = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int pre = (i > 0 ? dp[i - 1] : 0);
            if (s[i] == '('){
                dp[i] = pre + 1;
                if (!(dp[i] == 1 && i + 1 < n && s[i + 1] == ')')){
                    list2.add(i);
                }
            }else if (s[i] == ')'){
                tmp.add(i);
                dp[i] = pre - 1;
            }else {
                dp[i] = pre;
            }
            if (dp[i] == - 1){
                list.add(tmp);
                dp[i] = 0;
                tmp = new ArrayList<>();
            }
        }
        int remain = dp[n - 1], last = n - 1;
        for(int i = list2.size() - 1; i >= 0 && list2.get(i) == last; i--){
            last--;
            remain--;
            s[list2.get(i)] = '-';
            list2.remove(i);
        }
        Set<String> set = new HashSet<>();
        dfs(list, list2, set, 0, s, remain);
        return new ArrayList<>(set);
    }
    private static void dfs(List<List<Integer>> list, List<Integer> aft, Set<String> set, int i, char[] s, int remain){
        int len = list.size();
        if (i >= len){
            dfs2(aft, set, remain, 0, s);
            return;
        }
        for (Integer index : list.get(i)) {
            char pre = s[index];
            s[index] = '-';
            dfs(list, aft, set, i + 1, s, remain);
            s[index] = pre;
        }
    }
    private static void dfs2(List<Integer> list, Set<String> set, int remain, int i, char[] s){
        int len = list.size();
        if (len - i < remain)
            return;
        if (remain == 0){
            if (check(s)){
                StringBuilder sb = new StringBuilder();
                for (char c : s) {
                    if (c != '-'){
                        sb.append(c);
                    }
                }
                set.add(sb.toString());
            }
            return;
        }
        //删
        int mid = list.get(i);
        char pre = s[mid];
        s[mid] = '-';
        dfs2(list, set, remain - 1, i + 1, s);
        s[mid] = pre;
        //不删
        dfs2(list, set, remain, i + 1, s);
    }
    private static boolean check(char[] s){
        Deque<Character> queue = new ArrayDeque<>();
        for (char c : s) {
            if (c == '-')
                continue;
            if (c != '(' && c != ')')
                continue;
            if (queue.isEmpty()) {
                queue.push(c);
            } else {
                if (c == ')' && queue.peek() == '(') {
                    queue.pop();
                } else {
                    queue.push(c);
                }
            }
        }
        return queue.isEmpty();
    }
}